package UnionFind;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class _778_SwiminRisingWater {
    private int[][] grid;
    private int[] ids;
    private int rows;
    private int columns;
    private Set<int[]> vertex;
    private boolean[][] checked;
    private boolean stop;
    //time limit exceeded
    public int swimInWater(int[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.columns = grid[0].length;
        this.vertex = new HashSet<>();
        this.checked = new boolean[rows][columns];
        this.ids = new int[rows*columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                ids[grid[i][j]] = grid[i][j];
            }
        }
        int times = 0;
        int start = grid[0][0], end = grid[rows - 1][columns - 1];
        vertex.add(new int[]{0,0});
        while (!stop) {
            Set<int[]> tempSet = vertex;
            vertex = new HashSet<>();
            for (Iterator<int[]> it = tempSet.iterator(); it.hasNext();) {
                int[] tempNode = it.next();
                depthfirst(tempNode[0],tempNode[1],times);
            }
            times++;
        }
        return times-1;
    }

    public void depthfirst(int r, int c,int times) {
        if (r < 0 || r >= rows || c < 0 || c >= columns) {
        } else if (grid[r][c] > times) {
            int[] node = new int[2];
            node[0] = r;
            node[1] = c;
            vertex.add(node);
        } else {
            if (!checked[r][c]) {
                checked[r][c]=true;
                if (grid[r][c] == grid[rows - 1][columns - 1]) {
                    stop = true;
                }
                depthfirst(r - 1, c, times);
                depthfirst(r + 1, c, times);
                depthfirst(r,c-1,times);
                depthfirst(r,c+1,times);
            }
        }
    }

    public int find(int p) {
        while (p!=ids[p]) {
            p = ids[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);
        if(pid == qid) return;
        ids[qid] = ids[pid];
    }

}
